package com.example.leetcode;

/**
 * 出界的路径数 动态规划
 */
public class Demo0576 {
    public static void main(String[] args) {

    }

    /**
     * 1.状态: dp[i][j][k] 表示球移动 i 次之后位于坐标 (j, k) 的路径数量
     * 2.边界条件: dp[0][startRow][startColumn]=1;当(j,k)!=(startRow,startColumn) 时有 dp[0][j][k]=0
     * 3.转移方程: dp[i][j][k]再移动一步到dp[i+1][j‘][k’]
     *  a.当没出界时dp[i][j][k]加给dp[i+1][j‘][k’]
     *  b.当出界时dp[i][j][k]加给路径
     * @param m
     * @param n
     * @param maxMove
     * @param startRow
     * @param startColumn
     * @return
     */
    public static int findPaths1(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        /**
         * 定义dp[i][j][k]再移动一步到dp[i+1][j‘][k’]的四种情况
         * 定义路径数
         * 定义状态数组
         * 定义边界条件
         */
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][][] dp=new int[maxMove+1][m][n];
        dp[0][startRow][startColumn] = 1;

        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count=dp[i][j][k];
                    for (int[] direction : directions) {
                        int j1=j+direction[0];
                        int k1=k+direction[1];
                        if (j1>=0 && j1<m && k1>=0 && k1<n){
                            //在边界内
                            dp[i+1][j1][k1]=(dp[i+1][j1][k1]+count)%MOD;
                        }else {
                            //在边界外
                            outCounts=(outCounts+count)%MOD;
                        }
                    }
                }
            }
        }
        return outCounts;
    }

    public static int findPaths2(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        /**
         * 定义dp[i][j][k]再移动一步到dp[i+1][j‘][k’]的四种情况
         * 定义路径数
         * 定义状态数组
         * 定义边界条件
         */
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][] dp=new int[m][n];
        dp[startRow][startColumn] = 1;

        for (int i = 0; i < maxMove; i++) {
            int[][] dpNew=new int[m][n];
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count=dp[j][k];
                    for (int[] direction : directions) {
                        int j1=j+direction[0];
                        int k1=k+direction[1];
                        if (j1>=0 && j1<m && k1>=0 && k1<n){
                            //在边界内
                            dpNew[j1][k1]=(dpNew[j1][k1]+count)%MOD;
                        }else {
                            //在边界外
                            outCounts=(outCounts+count)%MOD;
                        }
                    }
                }
            }
            dp = dpNew;
        }
        return outCounts;
    }
}
